package UnitTest;

import java.util.Arrays;

/**
 * @Auther: Administrator
 * @Date: 2020/1/13/013 22 04
 * @Description: dp求解问题 最长等差数列 leetcode 1027
 */
public class LongestArithSeqLength {
    public static void main(String[] args) {
        int[] A = {3,6,9,12};
        int i  = longestArithSeqLength(A);
        System.out.println(i);
    }

    public static int longestArithSeqLength(int[] A) {
        int n = A.length;
        int[][] dp = new int[n][n];
        int[] index = new int[20001];
        Arrays.fill(index, -1);
        int max = 2;
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i],2);
            for (int j = i + 1; j < n; j++) {
                int first = A[i] * 2 - A[j];
                if (first < 0 || index[first] == -1) continue;
                dp[i][j] = dp[index[first]][i] + 1;
                max = Math.max(dp[i][j], max);
            }
            index[A[i]] = i;
        }
        return max;
    }

}
